package com.lgedu.homework;

/**
 * 0-1背包，计算最大价值  DP方程
 */
public class Gold {
    /**
     * 计算最大价值
     * @param values 物品的价值数组
     * @param weights 物品的重量数组
     * @param max 背包最大承重
     * @return
     */

    /***
     动态规划：0-1背包问题，可以想象成只有一个商品可选然后扩展到n个商品可选的问题上，一个商品可以认为是
     n个商品可选的基础解（元解）。
     当前新添加的商品分为可选和不可选：
     1. 不可选，当前dp的值直接使用上轮商品dp值
     2. 可选dp的最优解 = max (当前商品价值 + dp[上轮商品][当前重量 - 当前商品消耗重量])
     **/
    public static  int maxValue(int[] values,int[] personNume,int max){
        if(values==null|| values.length==0) return 0;
        if(personNume==null|| personNume.length==0) return 0;
        if(values.length!=personNume.length|| max<=0) return 0;

        System.out.println("dp数组横坐标-价值"+(values.length+1));
        System.out.println("dp数组纵坐标-重量"+(max+1));
        //dp数组  dp[i-1]  i从1开始
        int[][] dp=new int[values.length+1][max+1];

        //遍历物品对，价值-重量,表示是否选择这个商品
        for(int i=1;i<=values.length;i++){
            //使用的人数，等价于最大承重
            for(int j=1;j<=max;j++){
                //这个金矿不能选
                if(personNume[i-1]>j){
                    //不能选该物品 等于上轮的最大价值
                    dp[i][j]=dp[i-1][j];
                }
                //这个金矿能选
                    else {
                    //上轮的最大价值
                    int proValue=dp[i-1][j];
                    //选择该商品后的最大价值 = 当前商品的价值 + dp[上一轮商品选择][剩余可用人数] 所求得的最大值
                    int curValue=values[i-1]+dp[i-1][j-personNume[i-1]];
                    //两者取最大值
                    dp[i][j]=Math.max(proValue,curValue);

                }
                System.out.println(i+","+j+"==="+dp[i][j]);


            }
        }
        int mv=dp[values.length][max];
        //逆推找出装入背包的所有商品的编号（选的矿的编号）
        int j=max;
        String numStr="";
        for(int i=values.length;i>0;i--){
            //若果dp[i][j]>dp[i-1][j],这说明第i件物品是放入背包的（第i个矿挖）
            if(dp[i][j]>dp[i-1][j]){
                numStr = i+" "+numStr;
                j=j-personNume[i-1];
            }
            if(j==0)
                break;
        }
        System.out.println("选择的金矿有："+numStr);

        return mv;

    }

    public static void main(String[] args) {
        int[] values={800,150,700,100,600};
        int[] personNume={8,1,7,4,2};
        int max=10;
        System.out.println("挖出的最大储量是："+maxValue(values,personNume,max));
    }
}
